class Tree:
    def __init__(self, val):
        self.val = val
        self.flag = -1
        self.neighbors = {}


class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        out = []
        root = Tree('#')
        m = len(board)
        n = len(board[0])
        for index, word in enumerate(words):
            node = root
            for i in range(len(word)):
                if word[i] not in node.neighbors:
                    new_node = Tree(word[i])
                    node.neighbors[word[i]] = new_node
                    node = new_node
                else:
                    node = node.neighbors[word[i]]
            node.flag = index
        already_set = set()

        def dele(node, word, k):
            if k == len(word):
                if not node.neighbors:
                    return None
                else:
                    node.flag = -1
                    return node
            else:
                next_node = node.neighbors[word[k]]
                next_flag = dele(next_node, word, k + 1)
                if not next_flag:
                    node.neighbors.pop(word[k])
                    if not node.neighbors:
                        node = None
                return node

        def search(node, i, j):
            if board[i][j] in node.neighbors:
                next_node = node.neighbors[board[i][j]]
                if next_node.flag >= 0:
                    out.append(words[next_node.flag])
                    dele(root, words[next_node.flag], 0)
                for ux, uy in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
                    if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already_set:
                        already_set.add((ux, uy))
                        search(next_node, ux, uy)
                        already_set.remove((ux, uy))

        for i in range(m):
            for j in range(n):
                already_set = {(i, j)}
                search(root, i, j)
        return out


data = Solution()
board = [["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]]
words = ["oath", "pea", "eat", "rain"]
print(data.findWords(board, words))
board = [["o", "a", "b", "n"], ["o", "t", "a", "e"], ["a", "h", "k", "r"], ["a", "f", "l", "v"]]
words = ["oa", "oaa", "oa"]
print(data.findWords(board, words))
board = [["a", "a"]]
words = ["aa"]
print(data.findWords(board, words))
